#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define int long long




//void solve() {
//	int n;
//	string s;
//	cin >> n >> s;
//	vector<int> a(26);
//	vector<int> able(26,n);
//	int cnt = 0;
//	if (n & 1) {
//		cout << -1 << '\n';
//		return;
//	}
//	int i = 0, j = n - 1;
//	while (i < j) {
//		if (s[i] == s[j]) {
//			a[s[i] - 'a']++;
//			cnt++;
//			able[s[i] - 'a'] -= 2;
//		}
//		else {
//			able[s[i] - 'a'] -= 2;
//			able[s[j] - 'a'] -= 2;
//		}
//		i++;
//		j--;
//	}
//	bool ok = true;
//	int ans = 0;
//	for (int i = 0; i <= 25; i++) {
//		able[i] /= 2;
//		if (a[i]) {
//			ok &= (cnt >= 2 * a[i] || able[i] >= a[i]);
//			if (cnt < 2 * a[i] || able[i] >= a[i]) {
//				ans = max(ans, a[i]);
//			}
//		}
//	}
//	if (ok) {
//		cout << max(ans, cnt / 2 + (cnt & 1)) << '\n';
//	}
//	else
//		cout << "-1\n";
//	
//}
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	int t;
//	cin >> t;
//	while (t--) {
//		solve();
//	}
//
//	return 0;
//}

//int n, q;
//
//int head[100005], nxt[200005], to[200005], cnt;
//int depth[100005], lg[100005], st[100005][20];
//
//void dfs(int u, int fa) {
//	st[u][0] = fa;
//	depth[u] = depth[fa] + 1;
//
//	for (int i = 1; i <= lg[depth[i]]; i++) {
//		st[u][i] = st[st[u][i - 1]][i - 1];
//	}
//
//	for (int i = head[u]; i; i = nxt[i]) {
//		if (to[i] != fa)dfs(to[i], u);
//	}
//}
//
//void add(int u, int v) {
//	nxt[++cnt] = head[u];
//	head[u] = cnt;
//	to[cnt] = v;
//}
//
//int LCA(int x, int y) {
//	if (depth[x] < depth[y]) {
//		swap(x, y);
//	}
//	while (depth[x] > depth[y]) {
//		x = st[x][lg[depth[x] - depth[y]]];
//	}
//	if (x == y)
//		return x;
//	for (int i = lg[depth[x]]; i >= 0; i--) {
//		if (st[x][i] != st[y][i])
//			x = st[x][i], y = st[y][i];
//	}
//	return st[x][0];
//}
//
//int dis(int a, int b) {
//	int c = LCA(a, b);
//	return depth[a] + depth[b] - 2 * depth[c];
//}
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> n >> q;
//	for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
//	for (int i = 1,u,v; i < n; i++) {
//		cin >> u >> v;
//		add(u, v);
//		add(v, u);
//	}
//	dfs(1, 0);
//	for (int i = 1,a,b,c,d; i <= q; i++) {
//		cin >> a >> b >> c >> d;
//		int x = LCA(a, b);
//		int y = LCA(c, d);
//		if (dis(a, y) + dis(y, b) == dis(a, b) ||
//			dis(c, x) + dis(x, d) == dis(c, d))
//			cout << "Y\n";
//		else
//			cout << "N\n";
//	}
//	return 0;
//}